package 牛客网在线编程题库;

/**
 * 题目描述
 给定一个数组arr，返回子数组的最大累加和
 例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.
 题目保证没有全为负数的数据
 [要求]
 时间复杂度为O(n)O(n)，空间复杂度为O(1)O(1)

 示例1
 输入
 [1, -2, 3, 5, -2, 6, -1]
 返回值
 12
 */

public class _子数组的最大累加和问题 {
    public static void main(String[] args) {
        int[] arr = {1, -2, 3, 5, -2, 6, -1};
        int target = maxsumofSubarray(arr);
        System.out.println(target);
    }

    public static int maxsumofSubarray (int[] arr) {
        // 定义dp数组，以num[i]为结尾的最大子数组和为dp[i]
        int[] dp = new int[arr.length];
        // 初始化dp数组
        dp[0] = arr[0];
        for (int i = 1 ; i < dp.length ; i++) {
            dp[i] = Math.max(arr[i], dp[i - 1] + arr[i]);
        }
        // 目标最大累加和
        int sum = dp[0];
        for (int i = 1 ; i < dp.length ; i++) {
            if (dp[i] > sum) {
                sum = dp[i];
            }
        }
        return sum;
    }
}
